Corelab Seminar
2019-2020
Artemis Tsikiridis
On Core-Selecting and Core-Competitive Mechanisms for Binary
Single-Parameter Auctions
Abstract.
Our work concerns the class of core-selecting mechanisms. Such
mechanisms have been known to possess good revenue guarantees and some
of their variants have been used in practice especially for spectrum and
other public sector auctions. Despite their popularity, it has also been
demonstrated that these auctions are generally non-truthful. As a
result, current research has focused either on identifying
core-selecting mechanisms with minimal incentives to deviate from
truth-telling, such as the family of Minimum-Revenue Core-Selecting
(MRCS) rules, or on proposing truthful mechanisms whose revenue is
competitive against core outcomes. Our results contribute to both of
these directions. We start with studying the core polytope in more depth
and provide new properties and insights, related to the effects of
unilateral deviations from a given profile. We then utilize these
properties in two ways. First, we propose a truthful mechanism that is
O(logn)-competitive against the MRCS benchmark. Our result is the first
deterministic core-competitive mechanism for binary single-parameter
domains. Second, we study the existence of non-decreasing payment rules,
meaning that the payment of each bidder is a non-decreasing function of
her bid. This property has been advocated by the core related literature
but it has remained an open question if there exist MRCS non-decreasing
mechanisms. We answer the question in the affirmative, by describing a
subclass of rules with this property.